前端界面库展示

Appearance

Algorithms ​

Alt text

  • The linear search is that each element of an array is checked in order, from the lower bound to the upper bound, until the item is found, or the upper bound is reached.
DECLARE myList : ARRAY[0:9] OF INTEGER
DECLARE upperBound : INTEGER
DECLARE lowerBound : INTEGER
DECLARE index : INTEGER
DECLARE item : INTEGER
DECLARE found : BOOLEAN
upperBound ← 9
lowerBound ← 0
OUTPUT "Please enter item to be found"
INPUT item
found ← FALSE
index ← lowerBound
REPEAT
    IF item = myList[index] THEN
        found ← TRUE
    ENDIF
    index ← index + 1
UNTIL (found = TRUE) OR (index > upperBound)
IF found THEN
    OUTPUT "Item found"
ELSE
    OUTPUT "Item not found"
ENDIF
py
#Python program for Linear Search
#create array to store all the numbers
myList = [4, 2, 8, 17, 9, 3, 7, 12, 34, 21]
#enter item to search for
item = int(input("Please enter item to be found "))
found = False
for index in range(len(myList)):
    if(myList[index] == item):
        found = True
if(found):
    print("Item found")
else:
    print("Item not found")
  • A binary search is more efficient if a list is already sorted.
  • The value of the middle item in the list is first tested to see if it matches the required item, and the half of the list that does not contain the required item is discarded.
  • Then, the next item of the list to be tested is the middle item of the half of the list that was kept.
  • This is repeated until the required item is found or there is nothing left to test.

Alt text

Alt text

DECLARE myList : ARRAY[0:9] OF INTEGER
DECLARE upperBound : INTEGER
DECLARE lowerBound : INTEGER
DECLARE index : INTEGER
DECLARE item : INTEGER
DECLARE found : BOOLEAN
upperBound ← 9
lowerBound ← 0
OUTPUT "Please enter item to be found"
INPUT item
found ← FALSE
REPEAT
    index ← INT ( (upperBound + lowerBound) / 2 )
    IF item = myList[index] THEN
        found ← TRUE
    ENDIF
    IF item > myList[index] THEN
        lowerBound ← index + 1
    ENDIF
    IF item < myList[index] THEN
        upperBound ← index - 1
    ENDIF
UNTIL (found = TRUE) OR (lowerBound = upperBound)
IF found THEN
    OUTPUT "Item found"
ELSE
    OUTPUT "Item not found"
ENDIF

Bubble sort ​

  • This is a method of sorting data in an array into alphabetical or numerical order by comparing adjacent items and swapping them if they are in the wrong order.

Alt text

DECLARE myList : ARRAY[0:8] OF INTEGER
DECLARE upperBound : INTEGER
DECLARE lowerBound : INTEGER
DECLARE index : INTEGER
DECLARE swap : BOOLEAN
DECLARE temp : INTEGER
DECLARE top : INTEGER
upperBound ← 8
lowerBound ← 0
top ← upperBound
REPEAT
    FOR index = lowerBound TO top - 1
        Swap ← FALSE
        IF myList[index] > myList[index + 1] THEN
            temp ← myList[index]
            myList[index] ← myList[index + 1]
            myList[index + 1] ← temp
            swap ← TRUE
        ENDIF
    NEXT index
    top ← top -1
UNTIL (NOT swap) OR (top = 0)
py
#Python program for Bubble Sort
myList = [70,46,43,27,57,41,45,21,14]
top = len(myList)
swap = True
while (swap) or (top > 0):
    swap = False
    for index in range(top - 1):
        if myList[index] > myList[index + 1]:
            temp = myList[index]
            myList[index] = myList[index + 1]
            myList[index + 1] = temp
            swap = True
    top = top - 1 #output the sorted array
print(myList)

Insertion sort ​

  • An insertion sort sorts data in a list into alphabetical or numerical order by placing each item in turn in the correct position in a sorted list.

Alt text

DECLARE myList : ARRAY[0:8] OF INTEGER
DECLARE upperBound : INTEGER
DECLARE lowerBound : INTEGER
DECLARE index : INTEGER
DECLARE key : BOOLEAN
DECLARE place : INTEGER
upperBound ← 8
lowerBound ← 0
FOR index ← lowerBound + 1 TO upperBound
    key ← myList[index]
    place ← index - 1
    IF myList[place] > key THEN
        WHILE place >= lowerBound AND myList[place] > key
            temp ← myList[place + 1]
            myList[place + 1] ← myList[place]
            myList[place] ← temp
            place ← place - 1
        ENDWHILE
        myList[place + 1] ← key
    ENDIF
NEXT index

Stack ​

  • In programming terms, putting an item on top of the stack is called push and removing an item is called pop.

  • Item 3 was kept last, it was removed first.

  • This is exactly how the LIFO (Last In First Out) Principle works.

Alt text

Queue ​

  • A queue is a useful data structure in programming.
  • It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.
  • Queue follows the First In First Out (FIFO) rule - the item that goes in first is the item that comes out first.

Alt text

Linked list ​

  • A linked list is a linear data structure that includes a series of connected nodes.
  • Here, each node stores the data and the address of the next node.

Alt text

Binary tree ​

  • A binary tree is another frequently used ADT.

  • It is a hierarchical data structure in which each parent node can have a maximum of two child nodes.

  • There are many uses for binary trees; for example, they are used in syntax analysis, compression algorithms and 3D video games.

  • Figure shows the binary tree for the data stored in a list sorted in ascending order.

  • Each item is stored at a node and each node can have up to two branches with the rule if the value to be added is less than the current node branch left, if the value to be added is greater than or equal to the current node branch right.

Alt text

Graph ​

  • A graph is a non-linear data structure consisting of nodes and edges.
  • This is an ADT used to implement directed and undirected graphs.
  • A graph consists of a set of nodes and edges that join a pair of nodes.
  • If the edges have a direction from one node to the other it is a directed graph.

Alt text

  • For example, a graph of the bus routes in a town could be as follows.
  • The distance between each bus stop in kilometres is shown on the graph.

Alt text

Dictionary ​

  • Dictionary is an ADT that consists of pairs consisting of a key and a value, where the key is used to find the value.
  • Each key can only appear once.
  • Keys in a dictionary are unordered.
  • A value is retrieved from a dictionary by specifying its corresponding key.
  • The same value may appear more than once.
  • A dictionary differs from a set because the values can be duplicated.
py
studentdict = {
    "Leon": 27,
    "Ahmad": 78,
    "Susie": 64
}

Time and space complexity ​

  • Big O notation is a mathematical notation used to describe the performance or complexity of an algorithm in relation to the time taken or the memory used for the task.
  • It is used to describe the worst-case scenario.

Alt text

DescriptionExample
O(1)describes an algorithm that always takes the same time to perform the task deciding if a number is even or odd
O(N)describes an algorithm where the time to perform the task will grow linearlyin direct proportion to N, the number of items of data the algorithm is usinga linear search
O(N2)describes an algorithm where the time to perform the task will growlinearly in direct proportion to the square of N, the number of items ofdata the algorithm is usingbubble sort, insertion sort
O(2N)describes an algorithm where the time to perform the task doublesevery time the algorithm uses an extra item of datacalculation of Fibonacci numbersusing recursion (see Section 19.2)
O(Log N)describes an algorithm where the time to perform the task goes uplinearly as the number of items goes up exponentiallybinary search

0(n^2)

py
arr = [1,8,6, 4,3]
n = len(arr)
for i in range(n):
    for j in range(n-i-1):
        if arr[j] > arr[j+1] :
            arr[j],arr[j+1] = arr[j+1]，arr[j]
print(arr)

O(n)

py
n = int(input())
total = 0
for i in range(1,n):
    total += i
print(total)

O(1)

py
n = int(input())
total =(1+n)*n / 2
print(total)